//
// Description: 1588. 所有奇数长度子数组的和
// Created by Loading on 2021/8/29.
//

#include <bits/stdc++.h>

using namespace std;

/* 前缀和，O(n^2) */
int sumOddLengthSubarrays(vector<int> &arr) {
    // 前缀和数组，长度为 arr.size() + 1，第一个元素为 0
    vector<int> prefix_sum = {0};
    for (auto &x : arr) {
        prefix_sum.emplace_back(prefix_sum.back() + x);
    }

    int sum = 0;
    // 子数组开始位置枚举
    for (int i = 0; i < arr.size(); ++i) {
        // 子数组的长度枚举 1，3，5……
        for (int j = 1; j + i <= arr.size(); j += 2) {
            sum += prefix_sum[j + i] - prefix_sum[i];
        }
    }

    return sum;
}

/* 数学法，O(n) */
int sumOddLengthSubarrays_Math(vector<int> &arr) {
    /* 考虑每一个元素在所有长度为奇数的子数组中出现的次数 */
    int sum = 0;
    int n = arr.size();
    for (int i = 0; i < n; ++i) {
        // 当前位置左边和右边元素的个数
        int leftCount = i, rightCount = n - i - 1;
        /* 若要子数组总长度为奇数，则左边选取的个数和右边选取的个数奇偶性需相同 */
        // 同为奇数
        int leftOdd = (leftCount + 1) / 2, rightOdd = (rightCount + 1) / 2;
        // 同为偶数，因为 0 也是偶数，所以计算结果要 + 1
        int leftEven = leftCount / 2 + 1, rightEven = rightCount / 2 + 1;

        sum += (leftOdd * rightOdd + leftEven * rightEven) * arr[i];
    }

    return sum;
}

int main() {
    vector<int> arr = {1, 4, 2, 5, 3};
    int res = sumOddLengthSubarrays(arr);
    cout << res << endl;

    res = sumOddLengthSubarrays_Math(arr);
    cout << res << endl;

    return 0;
}